package org.example.BinaryTree;

public class The_closest_common_ancestor_of_binary_search_trees {
    public static TreeNode node = null;
    public static void main(String[] args) {
        //二叉搜索树的最近公共祖先

        //给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
        //百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
        //例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode root = new TreeNode(4);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        lowestCommonAncestor(root,node3,node1);
        if (node!=null){
            System.out.println(node.val);
        }else {
            System.out.println("null");
        }
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        search(root, p, q);
        return node;
    }

    public static void search(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || node!=null) return;
        if ((q.val >= root.val && root.val >= p.val) || (p.val >= root.val && root.val >= q.val)) {
            node = root;
            return;
        }
        if (root.val > p.val && root.val > q.val) search(root.left, p, q);
        if (root.val < p.val && root.val < q.val) search(root.right, p, q);
    }
}
